#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> myMergeAlgorithm(vector<int> & one, vector<int> & two); 
int main()
{
	typedef vector<int> IntVector;
	typedef IntVector::iterator IntVectorIt;

	size_t n,m;

	cout << "Enter the size of the first array for merging" << endl;
	cin >> n;
	cout << endl;
	cout << "Enter the size of the second array for merging" << endl;
	cin >> m;
	cout << endl;

	int first = n;
	int second = m;

	//Allocate vectors of sizes n, m and n+m
	//Define iterators and their initial and terminal values
	IntVector Vector1(n);
	IntVectorIt start1,end1,it1;
	start1 = Vector1.begin();
	end1 = Vector1.end();

	IntVector Vector2(m);
	IntVectorIt start2,end2,it2;
	start2 = Vector2.begin();
	end2 = Vector2.end();

	IntVector Vector3(n+m);
	IntVectorIt start3,end3,it3;
	start3 = Vector3.begin();
	end3 = Vector3.end();

	cout << "The result of merging by standard STL merge:" << endl << endl;

	//Enter n consecutive even numbers into vector 1
	int i=0;
	for(it1=start1;it1!=end1;it1++)
	{
		*it1=2*i;
		i++;
	}

	//Output numbers stored in vector 1
	cout << "The content of vector 1" << endl;
	for(it1=start1;it1!=end1;it1++)
		cout << *it1 << " ";
	cout << endl;
	
	//Enter m consecutive even numbers into vector 2
	i=0;
	for(it2=start2;it2!=end2;it2++)
	{
		*it2=2*i+1;
		i++;
	}
	
	//Output numbers stored in vector 2
	cout << "The content of vector 2" << endl;
	for(it2=start2;it2!=end2;it2++)
		cout << *it2 << " ";
	cout << endl;

	//Perform merging of vectors 1 and 2 into vector 3
	merge(start1,end1,start2,end2,start3);

	//Print out the result of merging
	cout << "The content of vector 3 after merging" << endl;
	for(it3=start3;it3!=end3;it3++)
		cout << *it3 << " ";
	cout << endl;
	cout << "_______________________________________________________________" << endl << endl;

	//My merge algorithm
	cout << "The result of merging by my implementation of merge algorithm:" << endl << endl;

	//Define all three vectors
	vector<int> vector1;
	vector<int> vector2;
	vector<int> vector3(100);
	
	//Initialize vectors one and two with respective even and odd numbers
	for(int i = 0; i < first; i = i++)
	{
		vector1.push_back(2*i);
	}

	for(int i = 0; i < second; i = i++)
	{
		vector2.push_back(2*i+1);
	}

	//Output numbers stored in vector 1
	cout << "The content of my vector 1" << endl;
	for(int i = 0; i < vector1.size(); i++) 
	{
		cout << vector1.at(i) << " ";
	}
	cout << endl;

	//Output numbers stored in vector 2
	cout << "The content of my vector 2" << endl;
	for(int i = 0; i < vector2.size(); i++) 
	{
		cout << vector2.at(i) << " ";
	}
	cout << endl;

	vector3 = myMergeAlgorithm(vector1, vector2);

	cout << "The content of my vector 3 after merging" << endl;
	for(int i = 0; i < vector3.size(); i++)
	{
		cout << vector3.at(i) << " ";
	}
	cout << endl;

	return 0;
}

vector<int> myMergeAlgorithm(vector<int> & one, vector<int> & two) 
{	
	vector<int> merge;

	int firstIterator = 0;
	int secondIterator = 0;
	

	for(int i = 0; i < one.size() + two.size(); i++)
	{
		//Check to see if either vector is exausted
		if (firstIterator == one.size()) 
		{
			while(secondIterator < two.size()) 
			{
				merge.push_back(two.at(secondIterator));
				secondIterator++;
			}
			i = one.size() + two.size() + 1;
			break;
		}
		else if (secondIterator == two.size()) 
		{
			while(firstIterator < one.size()) 
			{
				merge.push_back(one.at(firstIterator));
				firstIterator++;
			}
			i = one.size() + two.size() + 1;
			break;
		}

		//Compare indexes of each vector and add the smallest to the output vector
		if (one.at(firstIterator) <= two.at(secondIterator))
		{
			merge.push_back(one.at(firstIterator));
			firstIterator++;
		}else 
		{
			merge.push_back(two.at(secondIterator));
			secondIterator++;
		}
	}
	return merge;
}
